/**双向链表
1. 实现双向链表的基础操作：初始化、头插 / 尾插节点、指定位置插入、删除指定值节点、正向 / 反向遍历。
测试用例：插入 1->2->3 后，反向遍历结果应为 3->2->1。 */
#include <stdio.h>
#include <stdlib.h>

// 1. 双向链表节点结构定义
typedef struct DoubleLinkedListNode {
    int data;                          // 数据域
    struct DoubleLinkedListNode *prev; // 前驱指针
    struct DoubleLinkedListNode *next; // 后继指针
} DListNode, *PDListNode;

// 2. 初始化：创建哨兵节点（链表唯一标识，无需头/尾指针）
PDListNode DList_Init() {
    DListNode *node = (DListNode *)malloc(sizeof(DListNode));
    if (node == NULL) {
        return NULL;
    }

    node->prev = NULL;  
    node->next = NULL;  
    node->data = 0;     
    return node;
}

//创建节点
PDListNode DList_CreateNode(int data) {
    PDListNode node = (PDListNode)malloc(sizeof(DListNode));
    if (node == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 3. 头插节点：在第一个数据节点前插入（通过哨兵节点的next实现）
int DList_InsertHead(PDListNode node, int data) {//0 = 1 = 2
    if(node == NULL)//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（修改） 这里要加上！！
    {
        printf("哨兵为空，插入失败\n");
        return 1;
    }

    PDListNode newNode = DList_CreateNode(data);
    if(newNode == NULL)
    {
        printf("内存分配失败，头插失败\n");
        return 1;
    }
    newNode->prev = node;//新节点的前一个为哨兵
    newNode->next = node->next;//新节点的后一个为哨兵的下一个
    node->next->prev = newNode;//哨兵的下一个的前一个为新节点  最开始只有哨兵的时候 第一个节点就会被哨兵的prev指向
    node->next = newNode;//哨兵的下一个为新节点
    return 0;
}

// 4. 尾插节点：在最后一个数据节点后插入（通过哨兵节点的prev实现）
int DList_InsertTail(PDListNode node, int data) {
    if(node == NULL)//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!（修改） 这里要加上！！
    {
        printf("哨兵为空，插入失败\n");
        return 1;
    }
    PDListNode newNode = DList_CreateNode(data);

    if(newNode == NULL)
    {
        printf("内存分配失败，头插失败\n");
        return 1;
    }
    PDListNode tail =node;
    while (tail->next != NULL) {
            tail = tail->next;
        }

    newNode->next = NULL;
    // 尾节点后继指向新节点，新节点前驱指向尾节点
    newNode->prev = tail;//新节点的前一个为最后一个节点

    tail->next = newNode;//!!!!!!!!!(修改)加上这个！！！！！！！

    return 0;
    
}

// 5. 指定位置插入：在第pos个数据节点后插入（pos从1开始计数）
// 辅助函数：找到第pos个数据节点（内部使用，不对外暴露）
static PDListNode DList_FindPosNode(PDListNode node, int pos) {
    if (node == NULL || pos < 1) return NULL; //!!!!!!!!!!!!!!（修改） 这里要加上！！
    PDListNode index = node->next;// 从第一个数据节点开始
    //下面是修改
    int count = 1;
    while(count<pos && index!=NULL)
    {
        index = index->next;
        count++;
    }
    // 若count等于pos且未回到哨兵，说明找到 !!!!!
    return (count==pos && index!=NULL)?index:NULL;
}

int DList_InsertPos(PDListNode node, int pos, int data) {
//!!!!!!!!!!!!!!!!!!
// 特殊情况：pos=0等效头插（可选处理，此处按正常逻辑）
    if (pos == 0) {
        return DList_InsertHead(node, data);
    }

    PDListNode pos_node = DList_FindPosNode(node,pos);

    if (pos_node == NULL) {//!!!!!!!!很重要 （修改）
        printf("位置越界，插入失败\n");
        return 1;
    }

    PDListNode newNode = DList_CreateNode(data);
    if (newNode == NULL) return 1;//!!!!!!!!!!!!!!!

    newNode->next = pos_node;//新节点的下一个是pos_node
    newNode->prev = pos_node->prev;//新节点的前一个是第pos个节点的前一个
    pos_node->prev->next = newNode;//第pos个节点的前一个的下一个是新节点
    pos_node->prev = newNode;//第pos个节点的前一个是新节点
    return 0;
}

// 6. 删除所有值为target的节点
// (修改后). 删除所有值为target的节点！！！！！！！！！！！！！！！！！！！！！！！！！！
int DList_DeleteByValue(PDListNode *head, int target) {//!!!!!!!!!!!!带*
    if (*head == NULL) return 1;

    PDListNode curr = *head;
    PDListNode temp;

    //下面操作很nb！！！！！！！！！！！！！！！！！！
    while (curr != NULL) {
        temp = curr;
        curr = curr->next; // 先移动指针，避免删除后无法访问下一个节点

        if (temp->data == target) {
            if (temp->prev == NULL) { // 待删节点是头节点
                *head = temp->next;   // 更新头指针为下一个节点
                if (*head != NULL) {  // 若新头非空，其前驱置为NULL
                    (*head)->prev = NULL;
                }
            } else if (temp->next == NULL) { // 待删节点是尾节点
                temp->prev->next = NULL;     // 前驱节点后继置为NULL
            } else { // 待删节点是中间节点
                temp->prev->next = temp->next;
                temp->next->prev = temp->prev;
            }
            free(temp); // 释放节点内存
        }
    }
    return 0;
}

// 7. 正向遍历：从第一个数据节点到最后一个数据节点（通过哨兵的next遍历）
void DList_TraverseForward(PDListNode node) {//不打哨兵
    if(node==NULL){printf("链表为空\n");
    return;}
    PDListNode temp = node->next;
    printf("正向遍历：");
    while(temp != NULL)
    {
        if(temp->next != NULL)
        {
            printf(" %d <=> ",temp->data);
        }else{
            printf(" %d\n",temp->data);
        }
        temp = temp->next;
    }
}

// 8. 反向遍历：从最后一个数据节点到第一个数据节点
// void DList_TraverseBackward(PDListNode node) {//不打哨兵
//     PDListNode temp = node->prev;
//     while(temp->prev->next != NULL)
//     {
//         if(temp->prev->prev->next != NULL)
//         {
//             printf(" %d <=> ",temp->data);
//         }else{
//             printf(" %d\n",temp->data);
//         }
//         temp = temp->prev;
//     }
// }

// 8. 反向遍历：从车尾到车头（尾节点→头节点）  ！！！！！！修改后
void DList_TraverseBackward(PDListNode head) {
    if (head == NULL) {
        printf("反向遍历：链表为空\n");
        return;
    }

    // 先找到尾节点（next=NULL的节点）
    PDListNode tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }

    // 从尾节点向前遍历（prev指针）
    PDListNode curr = tail;
    printf("反向遍历：");
    while (curr->prev != NULL) {
        printf("%d", curr->data);
        curr = curr->prev;
        if (curr->prev != NULL) printf(" <=> "); // 最后一个节点后不加箭头
    }
    printf("\n");
}

// 9. 销毁链表：释放所有数据节点和哨兵节点
void DList_Destroy(PDListNode *node) {//*node 很重要！！！！！！！
    if(node==NULL)
    {
        return ;
    }
    PDListNode curr = *node; // 指向当前要释放的节点
    PDListNode next;         // 保存下一个节点的指针，防止释放后无法访问
    while(curr!=NULL)
    {
        next = curr->next; // 先记录下一个节点 
        free(curr);        // 释放当前节点的内存
        curr = next;       // 移动到下一个节点
    }
     *node = NULL; // 链表头指针置空，避免野指针
}

// 10. 测试函数：验证所有操作
int main() {
    //插入 1->2->3 后，反向遍历结果应为 3->2->1。
    PDListNode node = DList_Init();
    DList_InsertTail(node,1);

    printf("%d\n",node->next->data);

    DList_InsertTail(node,2);

    printf("%d\n",node->next->next->data);

    DList_InsertTail(node,3);

    printf("%d\n",node->next->next->next->data);


    printf("正向遍历\n");

    DList_TraverseForward(node);
    printf("反向遍历\n");
    DList_TraverseBackward(node);
    return 0;
}